package com.datastructures2.字符串.子字符串查找;


import com.datastructures2.字符串.字符串排序.Quick3string;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

/**
 * 后缀数组（初级）查找最长公共子串
 * @author MaoLin Wang
 * @date 2020/3/316:51
 */
public class SuffixArray {
    private final String[] suffixes;
    /**
     * 字符串（或后缀数组）的长度
     */
    private final int N;

    public SuffixArray(String s) {
        N=s.length();
        suffixes=new String[N];
        for (int i = 0; i < N; i++) {
            suffixes[i]=s.substring(i);
        }
        Quick3string.sort(suffixes);
    }

    public int length(){
        return N;
    }
    public String select(int i){
        return suffixes[i];
    }
    public int index(int i){
        return N-suffixes[i].length();
    }

    /**
     * 返回suffix[i]和suffix[i-1]的最长公共前缀
     * @param i
     * @return
     */
    public int lcp(int i){
        return lcp(suffixes[i],suffixes[i-1]);
    }

    /**
     * 两个字符串的最长公共前缀
     * 其中 s=t+1
     * @param s
     * @param t
     * @return
     */
    private int lcp(String s, String t) {
        int N=Math.min(s.length(),t.length());
        for (int i = 0; i < N; i++) {
            if (s.charAt(i)!=t.charAt(i)){
                return i;
            }
        }
        return N;

    }

    /**
     * 小于键key的后缀数量
     * @param key
     * @return
     */
    public int rank(String key){
        int left=0,right=N-1;
        while (left<=right){
            int mid=(left+right)/2;
            int result=key.compareTo(suffixes[mid]);
            if (result<0){
                right=mid-1;
            }else if (result>0){
                left=mid+1;
            }else {
                return mid;
            }
        }
        return left;
    }

    /**
     * 返回最长公共子串
     * @return
     */
    public String lrs(){
        String lrs="";
        for (int i = 1; i < N; i++) {
            int length=lcp(i);
            if (length>lrs.length()){
                lrs=select(i).substring(0,length);
            }
        }
        return lrs;
    }

    /**
     * 上下文中的关键词的索引用例
     * @return
     */
    public String KWIC(){
        In in = new In();
        int context = Integer.parseInt("S");
        String text = in.readAll().replaceAll("\\s+", " ");
        int n = text.length();

        for(edu.princeton.cs.algs4.SuffixArray sa = new edu.princeton.cs.algs4.SuffixArray(text); StdIn.hasNextLine(); StdOut.println()) {
            String query = StdIn.readLine();

            for(int i = sa.rank(query); i < n; ++i) {
                int from1 = sa.index(i);
                int to1 = Math.min(n, from1 + query.length());
                if (!query.equals(text.substring(from1, to1))) {
                    break;
                }

                int from2 = Math.max(0, sa.index(i) - context);
                int to2 = Math.min(n, sa.index(i) + context + query.length());
                StdOut.println(text.substring(from2, to2));
            }
        }
        return "";
    }

    public static void main(String[] args) {
         String s="asdncvxnjkasddadccccjnjnkjncccc";
         SuffixArray suffixArray=new SuffixArray(s);
        String lrs = suffixArray.lrs();
        System.out.println(lrs);


    }
}
